1. Technical Field
The present invention relates generally to digital data processing systems, and, in particular, to structures and methods in digital data processing systems for managing available memory resources.
2. Background Art
In general, in the descriptions that follow, we will italicize the first occurrence of each special term of art which should be familiar to those skilled in the art of digital data processing systems. In addition, when we first introduce a term that we believe to be new or that we will use in a context that we believe to be new, we will bold the term and provide the definition that we intend to apply to that term. Since our invention is specifically intended for use in digital data processing systems, we will often use terms that are well known to those skilled in this particular art. For example, with respect to an individual element of information stored at a particular address in a memory component of such a system, we will typically use the term pointer to refer, not to the element per se, but to a separate and distinct element that contains the address of the referenced element. Other common terms of art that we may use include: b for bit and B for byte, msb for most significant bit and lsb for least significant bit; and MB for megabyte.
From at least the 1940's, programmers of digital data processing systems have employed various logical structures to manage available, unallocated memory resources. In one popular arrangement, a memory initialization process, activated during system initialization, partitions the available memory into a set of blocks, each comprising a conveniently-sized, continuous range of addresses in the memory that are not presently allocated to an active process. The process then constructs a linked list of these free blocks by storing into a pre-assigned address within each block a pointer or forward link to the immediately succeeding block on the list. In general, the primary access point of the list is a header which contains, at a minimum, a forward link for storing a pointer to the block at the head of the free list. If desired, the header may also include a backward link containing a pointer to the block at the tail of the free list. For convenience, the header may contain other information related to the status of the free list, such as the number of blocks currently on the free list.
In a typical modern digital data processing system incorporating a conventional, commercially available microprocessor, such as the Pentium® 4 from Intel Corporation, the memory component is hierarchically-organized into a plurality of separate and distinct layers, e.g., a high-speed, but relatively small level A, and a slower but larger level B. In such a system, it is most efficient to maintain the header in a memory resource that can be rapidly accessed by the central processing unit, which is typically a data cache or other high-speed circuit such as a register array or the like. For the purposes of our invention, we think of the resources at level A as being accessible in a single clock cycle, whereas accesses to the main memory component at level B require multiple clock cycles. Despite the expenditure of considerable resources by memory designers, we expect that this performance differential will only increase as advances in semiconductor manufacturing processes and deep-pipelining techniques enable the processor component to operate at significantly higher clock frequencies vis-à-vis the main memory component.
Shown by way of example in FIG. 1 is a hierarchically-organized memory 2 in which unallocated blocks of memory are managed by means of a free list 4 maintained, for example, at level B of the memory 2. Constructed in accordance with a known prior art memory initialization process, the exemplary list is comprised of: a first block, BA 6, (often called the tail of the list) having a null forward link (“Link”) indicating that there are no lower blocks on the free list 4; a next higher block BB 8 having a forward Link that points to the next lower block BA 6; and so on up the list through blocks BC 10, BD 12, . . . , and BY 14 to a top block BZ 16, (often called the head of the list) having a forward Link that points to the next lower block BY 14. Within a header 18, maintained at level A of the memory 2, a forward link, Head 20, points to the free block at the head of the free list 4, namely BZ 16, and a backward link, Tail 22, points to the free block at the tail of the free list 4, which, in this example, is BA 6.
Note: In the several figures we will use a dashed connecting line to indicate that additional blocks may be present in the corresponding link but have not been shown to avoid making the illustrations unnecessarily complex.
In response to receiving from an active process, say Process_A, a request to allocate a block of free memory, a memory allocation process will typically allocate the block at the head of the free list. For the example shown in FIG. 1, block allocation can be as simple as:                1. Retrieving from Head 20 the pointer to the block at the head of the free list 4, namely block BZ 16;        2. Retrieving from the block BZ 16 the Link to the next lower block on the free list 4, namely block BY 14; and        3. Storing the pointer to the block BY 14 in Head 20.        
Note: Various methods have been proposed for informing Process_A of the location (and size) of the allocated block, including just providing to Process_A the pointer to the block. In some applications, it may be desirable to have the memory allocation process link the newly allocated block onto a list of blocks “owned” by Process_A.
Thus, in a hierarchically-organized memory such as that shown in FIG. 1, block allocation requires a minimum of three memory accesses:
                1. a read cycle at level A of the memory;        2. a read cycle at level B of the memory; and        3. a write cycle at level A of the memory.        
In response to receiving from an active process a request to deallocate an allocated block of memory, a memory deallocation process will typically return the block to the head of the free list. Continuing with the example shown in FIG. 1 and assuming that Process_A has requested deallocation of the just-allocated block BZ 16, deallocation can be as simple as:                1. Retrieving from Head 20 the pointer to the block at the head of the free list 4, namely block BY 14;        2. Storing into the forward Link of the block BZ 16 the pointer to the block BY 14; and        3. Storing the pointer to the block BZ 16 in Head 20.        
Note: If, as noted above, the memory allocation process maintains for Process_A a list of blocks owned by that process, the memory deallocation process is responsible for unlinking from Process_A's list the block that is being deallocated.
Thus, in a hierarchically-organized memory such as that shown in FIG. 1, block deallocation also requires a minimum of three memory accesses:
                1. a read cycle at level A of the memory;        2. a write cycle at level B of the memory; and        3. a write cycle at level A of the memory.        
Although we have illustrated the memory 2 as being comprised of only levels A and B, this is by way of example only and is not intended to suggest that the memory 2 is limited to only 2 levels or that the free list 4 and header 18 cannot be constructed so as to be stored together at the same level or separated by more than a single level. Furthermore, although we have selected as the context of this description a relatively large scale system which typically includes an operating system, other embodiments are certainly possible, including embedded systems which typically have no separate and distinct operating system, as well as purely hardware instantiations in which suitably programmed state machines accomplish the essential memory management processes. As will be clear to those skilled in this art, such decisions will be influenced by numerous factors, including hardware cost and system performance.
We submit that what is needed is a more efficient structure and method for managing available memory resources, and, in particular, one in which fewer accesses to the main memory component are required, on the average, to allocate and deallocate blocks of available memory.